package com.gxc.integer;

/**
 * 3129. 找出所有稳定的二进制数组 I
 * 给你 3 个正整数 zero ，one 和 limit 。
 *
 * 一个
 * 二进制数组
 *  arr 如果满足以下条件，那么我们称它是 稳定的 ：
 *
 * 0 在 arr 中出现次数 恰好 为 zero 。
 * 1 在 arr 中出现次数 恰好 为 one 。
 * arr 中每个长度超过 limit 的子数组,都 同时 包含 0 和 1 。
 * 请你返回 稳定 二进制数组的 总 数目。
 *
 * 由于答案可能很大，将它对 109 + 7 取余 后返回。
 */
public class NumberOfStableArrays {

    public static void main(String[] args) {
       /* System.out.println(handle2(1, 1, 2));
        System.out.println(handle2(1, 2, 1));
        System.out.println(handle2(3, 3, 2));*/
        System.out.println(handle2(65, 15, 15));
        System.out.println(handle3(65, 15, 15));
    }

    public static int handle(int zero, int one, int limit) {
        if (limit >= zero+one) {
            int min = Math.min(one, zero);
            long res = 1;
            for (int i = 1; i <= min; i++) {
                res = res * (zero + one - i + 1) /i % (1000000007);
            }
            return (int) res;
        }
        int[] arr = new int[zero+one];
        return recursion(zero, one, limit, arr, 0, 0);
    }

    public static int recursion(int zero, int one, int limit, int[] arr, int index, int maxSame) {
        if (zero==0 && one == 0) return 1;

        if (maxSame == limit) {
            if (arr[index-1] == 0) {
                if (one == 0) return 0;
                arr[index] = 1;
                return recursion(zero, one-1, limit, arr, index+1, 1);
            } else {
                if (zero == 0) return 0;
                arr[index] = 0;
                return recursion(zero-1, one, limit, arr, index+1, 1);
            }
        }

        int prev = -1;
        if (index>0) {
            prev = arr[index-1];
        }
        if (zero!=0 && one!=0) {
            arr[index] = 1;
            int a = recursion(zero, one-1, limit, arr, index+1, prev==1?(maxSame+1):1);

            arr[index] = 0;
            int b = recursion(zero-1, one, limit, arr, index+1, prev==0?(maxSame+1):1);
            return a + b;
        } else if (zero==0) {
            arr[index] = 1;
            return recursion(zero, one-1, limit, arr, index+1, prev==1?(maxSame+1):1);
        } else {
            arr[index] = 0;
            return recursion(zero-1, one, limit, arr, index+1, prev==0?(maxSame+1):1);
        }
    }

    /**
     * 当前位置已0 结尾和当前位置已1结尾
     * @param zero
     * @param one
     * @param limit
     * @return
     */
    public static int handle2(int zero, int one, int limit) {
        int a = 1000000007;
        int[][] dp0 = new int[zero+1][one+1];
        int[][] dp1 = new int[zero+1][one+1];

        for (int i = 1; i <= Math.min(zero, limit); i++) {
            dp0[i][0] = 1;
        }
        for (int i = 1; i <= Math.min(one, limit); i++) {
            dp1[0][i] = 1;
        }
        for (int i = 1; i <= zero; i++) {
            for (int j = 1; j <= one; j++) {
                //以1结尾的  dp1 可以随时加0  以0结尾的 需要减去连续limit的0
                dp0[i][j] = dp1[i-1][j] + dp0[i-1][j];
                //减去不符合稳定的，已1结尾连续limit的0
                if (i>limit) {
                    dp0[i][j] = dp0[i][j] - dp1[i-1-limit][j];
                }
                if (dp0[i][j]%a != ( (dp0[i][j]%a + a)  % a)) System.out.println(dp0[i][j]);;
                //  (dp0[i][j]%a + a)  % a    p0[i][j] = dp0[i][j] - dp1[i-1-limit][j];  会导致负数
                dp0[i][j] = (dp0[i][j]%a + a)  % a;

                //以0结尾的  dp0 可以随时加1  以0结尾的 需要减去连续limit的1
                dp1[i][j] = dp0[i][j-1] + dp1[i][j-1];
                if (j>limit) {
                    dp1[i][j] = dp1[i][j] - dp0[i][j-1-limit];
                }
                dp1[i][j] = (dp1[i][j]%a + a)%a;
            }
        }

        return (dp0[zero][one] + dp1[zero][one])%a;
    }

    public static int handle3(int zero, int one, int limit) {
        int a = 1000000007;
        int[][] dp0 = new int[zero+1][one+1];
        int[][] dp1 = new int[zero+1][one+1];

        for (int i = 1; i <= Math.min(zero, limit); i++) {
            dp0[i][0] = 1;
        }
        for (int i = 1; i <= Math.min(one, limit); i++) {
            dp1[0][i] = 1;
        }
        for (int i = 1; i <= zero; i++) {
            for (int j = 1; j <= one; j++) {
                //以1结尾的  dp1 可以随时加0  以0结尾的 需要减去连续limit的0
                dp0[i][j] = dp1[i-1][j] + dp0[i-1][j];
                //减去不符合稳定的，已1结尾连续limit的0
                if (i>limit) {
                    dp0[i][j] = dp0[i][j] - dp1[i-1-limit][j];
                }
                dp0[i][j] = dp0[i][j]%a ;
                //以0结尾的  dp0 可以随时加1  以0结尾的 需要减去连续limit的1
                dp1[i][j] = dp0[i][j-1] + dp1[i][j-1];
                if (j>limit) {
                    dp1[i][j] = dp1[i][j] - dp0[i][j-1-limit];
                }
                dp1[i][j] = dp1[i][j]%a;
            }
        }

        return (dp0[zero][one] + dp1[zero][one])%a;
    }

    //dp
    class Solution {
        public int numberOfStableArrays(int zero, int one, int limit) {
            final long MOD = 1000000007;
            long[][][] dp = new long[zero + 1][one + 1][2];
            for (int i = 0; i <= Math.min(zero, limit); i++) {
                dp[i][0][0] = 1;
            }
            for (int j = 0; j <= Math.min(one, limit); j++) {
                dp[0][j][1] = 1;
            }
            for (int i = 1; i <= zero; i++) {
                for (int j = 1; j <= one; j++) {
                    if (i > limit) {
                        dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit - 1][j][1];
                    } else {
                        dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
                    }
                    dp[i][j][0] = (dp[i][j][0] % MOD + MOD) % MOD;
                    if (j > limit) {
                        dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0] - dp[i][j - limit - 1][0];
                    } else {
                        dp[i][j][1] = dp[i][j - 1][1] + dp[i][j - 1][0];
                    }
                    dp[i][j][1] = (dp[i][j][1] % MOD + MOD) % MOD;
                }
            }
            return (int) ((dp[zero][one][0] + dp[zero][one][1]) % MOD);
        }
    }


}
